1. The Field of the Invention
The present invention relates to an operating circuit for Galois field included in am error correcting circuit which operates to code and decode an error detecting code or an error correcting code appearing when transmitting or recording and reproducing digital information, in particular, a Reed-Solomon code.
2. Description of the Related Arts
In general, a coder for coding digital information and a decoder for decoding transmitted or recorded or reproduced data will be referred to as an error correcting circuit.
In order to perform coding and decoding in the error correcting circuit, an operating circuit on a Galois field (referred to as a Galois field operating circuit) is an essential element.
The Galois field operating circuit is required to perform addition, subtraction and multiplication on the Galois field. If the number of the elements on the Galois field is a power of 2, subtraction on the Galois field is equivalent to addition on the Galois field.
The digital information recording and reproducing apparatus such as a compact disk or a digital audio tape recorder performs an error correction based on 2.sup.8 =256 elements on the Galois field. Hence, the Galois field operating circuit is required to perform only an addition and a multiplication on the Galois field.
The inventors of the present invention know a Galois field operating circuit having one addition and multiplication unit which takes the operating steps of receiving an input of two elements X and Y of the Galois field, performing an addition like Z=X+Y and a multiplication like Z=X.times.Y and feeding an operational result Z, where + and .times. denote addition and multiplication on the Galois field, respectively.
The above-mentioned Galois field operating circuit is capable of performing just one of an addition and a multiplication at a time. The use of this Galois field operating circuit makes it possible to perform any kind of calculation by repeating an addition and a multiplication.
For example, in order to calculate a determination of a two-dimensional matrix (a.sub.ij), three operations are executed in series as follows; EQU F=a.sub.11 .times.a.sub.22 EQU G=a.sub.21 .times.a.sub.12 EQU Z=F+G
where F and G denote intermediate results stored in an internal register provided inside of the error correcting circuit.
However, as the data transfer speed becomes faster, the error correction is required to be faster. With the higher recording density of a digital video cassette recorder (VCR), the error rate is made higher and higher in the recorder. Hence, such a device as a VCR requires a higher error correcting capability. In order to meet the need, there has been proposed a Galois field operating circuit for performing two or more operations at a time.
The inventors of the present invention know another Galois field operating circuit which is arranged to solve a shortcoming of the first Galois field operating circuit just described above.
The second Galois field operating circuit includes two Galois field multipliers and one Galois field adder. This Galois field operating circuit operates to receive four elements X1, X2, Y1 and Y2 of the Galois field, to perform an operation of Z=X1.times.X2+Y1.times.Y2, and feed the operational result Z. For example, to calculate a determination of two-dimensional matrix, the following operations can be taken. EQU Z=a.sub.11 .times.a.sub.22 +a.sub.21 .times.a.sub.12
The above-mentioned second Galois field operating circuit is capable of calculating a determination of two-dimensional matrix three times as fast as the first Galois field operating circuit.
However, the second Galois field operating circuit is incapable of performing an addition of X1+X2 on the Galois field and an addition of Y1+Y2 on the Galois field. For example, in order to obtain a sum of the four elements P, Q, R and S on the Galois field, it is necessary to perform three calculations of EQU F=P.times.1+Q.times.1 EQU G=R.times.1+S.times.1 EQU Z=F.times.1+G.times.1
Moreover, the second Galois field operating circuit is also incapable of outputting two operational results of X1.times.X2 and Y1.times.Y2 independently. Hence, in order to obtain a product of the four elements P, Q, R and S of the Galois field, it is necessary to perform three operations of EQU F=P.times.Q+O.times.O EQU G=R.times.S+0.times.0 EQU Z=F.times.G+0.times.0
It means that one of two multipliers is not used, which disadvantageously leads to an obstacle for an efficient operation.
In the field of error correction, a method for solving an error location polynomial and an error value polynomial has been well known as a method for deriving a location and a value of an error.
In order to solve an error locator polynomial, assuming that a code length of an input data train is n and a primitive element of a Galois field GF(q.sup.m) (where q: a prime number, m: a natural number) is .alpha., then .alpha..sup.-i (i=0, 1, 2, . . . n-1) is sequentially substituted in the error locator polynomial for obtaining the roots. In order to execute the operation, there are two ways of using dedicated software and Chien search on the hardware. After computing the location and the value of an error through either of these two ways, the input data train is corrected and then the corrected data is output.
At the present time, as the information to be treated becomes larger and larger, it is more and more desirous that the error correction be made more faster.
However, the above-mentioned error correcting method based on the software requires an enormous number of steps when performing a correction on a high-degree level, thereby disadvantageously lowering the processing speed.
The above-mentioned error correcting method using the Chien search in hardware is arranged to match the delayed input data train to the corrected data train in phase before outputting data and to correct an error symbol at a time when it is found. As such, assuming that the input data are D.sub.n-1, D.sub.n-2, D.sub.n-3 . . . . D.sub.1, D.sub.0, the delayed input data train is sequentially output from the side of D.sub.n-1, while the Chien search operates to sequentially check the data from the side of D.sub.0. Hence, disadvantageously, the sequence of the input data train is not matched to the sequence of the output data having error patterns.
In order to solve the foregoing disadvantages, when coefficients of an error locator polynomial are input to a Chien search circuit, coefficient multipliers are provided before those coefficients are applied to the Chien search circuit. This results in disadvantageously making the circuit bulkier. Further, it is possible to start from .alpha..sup.-(n-1) an error location to be substituted for executing the Chien search in the hardware. For that purpose, it is necessary to fix a code length n to be treated in the circuit. This results in impairing the wide availability of the error correcting circuit and making it impossible to constantly set an optimal strategy.
A digital video cassette recorder (VCR) developed for a broadcasting purpose is beneficial since it is able to record a high-quality image as well as to keep the quality of the image constant even though the image is dubbed many times. However, the broadcasting digital VCR operates to record and reproduce the image at a relatively low recording density for suppressing the occurrence of an error appearing when reproducing an image. This result in increasing the consumption of the tape.
In order to make the digital VCR more available for consumer use, it is necessary to develop a signal processing method for suppressing the consumption of tape. Hence, some relevant techniques such as an image compressing technique and a high-density recording technique are under active study.
However, the image compression eliminates redundancy information from the image although it originally provides the redundancy. Hence, it is difficult to conceal the miscorrection. Further, since the inferior circumstance and the high-density recording increase the errors appearing when reproducing an image, the digital VCR for consumer use is required to provide a high error correcting capability.
Further, the image compression serves to compress the original image data into about 1/8 of the data. Hence, the consumer VCR just needs 1/8 the speed for correction as the professional digital VCR. However, the consumer VCR needs ten times the speed for a correction as a digital audio apparatus such as a digital audio tape recorder (DAT).
The inventors of the present invention know an arrangement of the error correcting circuit, which solves above-mentioned difficulty, and which is arranged to have an input unit, an operating unit connected to the input unit, an output unit connected to the operating unit, and a delaying unit connected to both of the input unit and the output unit.
An operation of the above-mentioned error correcting circuit will be described below.
The above-mentioned error correcting circuit is arranged to divide a correcting process into three stages of
(1) generating a syndrome and erasure locator, PA1 (2) deriving an error location and an error value and checking a corrected result, and PA1 (3) outputting the corrected result and executing the three stages through one pipeline.
For example, at the stage (1) of generating a syndrome and erasure locator, the input unit operates to generate a syndrome and an erasure locator while one code passes through the circuit and to pass the generated syndrome and the erasure locator to the next pipeline.
At the next stage (2) of deriving an error location and an error value and checking the corrected result, the operating unit operates to derive an error value from the syndrome and the erasure locator according to a correcting program configured on the decoding strategy and to check the corrected result from the derived error location and error value and then to pass the checked result to the next pipeline.
At the next stage (3) of outputting the corrected result, the output unit operates to add an error value to the data corresponding to the error location derived at the previous stage and to terminate the correcting process.
As described above, a method for deriving an error location and an error value from the syndrome and the erasure locator according to the correcting program makes it possible to execute such a strategic decoding as flexibly optimizing the correcting algorithm by means of information such as an error inclination and a number of erasure flags.
However, if the number of errors to be corrected is relatively small (such as three error correction or four corrections for erasure), the above-mentioned error correcting circuit makes a small amount of calculations in the stage (2) of deriving an error location and an error value and checking the corrected result. Hence, the above-mentioned error correcting circuit facilitates termination of the process of the stage (2) of deriving an error location and an error value before one code passes through the error correcting circuit. This makes it possible to perform a fast processing. However, to enhance the correcting capability such as four error corrections or eight corrections for erasure, for instance, the number of calculations consumed in the error correcting circuit is surprisingly increased, thereby lowering the correcting speed. It means that the above-mentioned error correcting circuit has difficulty in enhancing the correcting speed if the correcting capability is made higher.
In general, as a recording density of digital data becomes higher and higher, several kinds of methods are used for correcting a data error.
For example, in a digital video cassette recorder (VCR), it is known that erroneous correction has an adverse effect on a quality of image than an interpolation can be executed as a result of appearance of an uncorrectable error.
As a method for preventing erroneous correction, if there exists a syndrome sufficiently off from an error and which is not used for obtaining a location and a size of the error, the verification on the syndrome is executed.
The inventors of the present invention know a method for preventing erroneous correction, assuming that the input data is D.sub.n-1, D.sub.n-2, D.sub.n-3 . . . . . D.sub.2, D.sub.1 and D.sub.0, one syndrome S.sub.x can be obtained by sequentially applying the input data D.sub.n-1, D.sub.n-2, D.sub.n-3 . . . . D.sub.2, D.sub.1, and D.sub.0 in a syndrome operating circuit. The syndrome S.sub.x is output as follows when the last input data D.sub.O is read in a flip-flop included in the syndrome operating circuit; EQU S.sub.x =D.sub.n-1 .alpha..sup.x(n-1) +D.sub.n-2 .alpha..sup.x(n-2) +D.sub.n-3 .alpha..sup.x(n-3) +. . . . +D.sub.2 .alpha..sup.2x +D.sub.1 .alpha..sup.x +D.sub.0
where + denotes an addition on a Galois field (hereafter, it means the same in all the expressions indicated below), and n denotes a length of a code and .alpha. denotes a primitive element of the Galois field GF(q.sup.m).
If no error exists in the data train, the syndrome is made zero and the resulting value is as indicated below; EQU S.sub.x =D.sub.n-1 .alpha..sup.x(n-1) +D.sub.n-2 .alpha..sup.x(n-2) +D.sub.n-3 .alpha..sup.x(n-3) +. . . . +D.sub.2 .alpha..sup.2x +D.sub.1 .alpha..sup.x +D.sub.0
where D.sub.i ' denotes a value of an error of the input data D.sub.i. If an error exists, D.sub.i ' denotes its value and if no error exists, it is zero. The location of an error D.sub.i ' in the code can be uniquely expressed by .sigma..sup.i, where .alpha..sup.i is referred to as an error locator.
As such, it is determined that the correction is terminated when the error value D.sub.n-1 ' to D.sub.0 ' of each data obtained by an operation is sequentially input to the syndrome operating circuit and the result is matched to the syndrome S.sub.x.
As a method for obtaining the location and the value of an error, an error locator polynomial and an error evaluator polynomial may be used.
This method is a method of executing a Chien search arranged to sequentially substitute .alpha..sup.-i (i=0, 1, 2 . . . ., n-1) to the error locator polynomial and deriving an error location and an error value.
However, as a method for preventing the above-mentioned erroneous correction, when generating a syndrome and verifying the corrected-result, the data train is operated on the side of the input data D.sub.n-1 and is sequentially calculated from the input data D.sub.0 when performing the Chien search. Hence, until the Chien search is terminated, it is necessary to wait for the verification. This results in disadvantageously increasing the processing time for correcting an error.
The inventors of the present invention know an error correcting device which is so arranged that by assuming a number of correctable symbols is K (an integer in the range of 1.ltoreq.K), the error location and the error value obtained by an operation and analyzing unit are stored in each pair of K storage elements. An output of the storage element for storing an error size is applied into a selecting circuit which serves to output an input value or zero in response to a control signal. On the other hand, an address counter operates to count a code length of a data train and to send the count to a comparator. The comparator receives the outputs of K storage elements each for storing an error location. The comparator constantly compares the count of the address counter and with the error location sent from the K storage elements.
The address counter is set to output all the error locations in the data train. Hence, if the error location derived by the operation and analyzing unit is inside of the code, it is certain that the value of one storage element is matched to the count of the address count at one time. Only when both are matched to each other, the comparator sends a control signal to the selecting circuit connected to the storage element for storing an error value for the error location so that the selecting circuit may output the error value. The outputs of the selecting circuits collectively pass through a multiplexer. Since the selecting circuit sends zero as the other output, the multiplexer outputs only one-symbol data. The one-symbol data is added at the symbol to the same location of the delayed input data through the adder for correcting the data train.
However, assuming that the number of correctable symbols is K, the error correcting circuit requires to prepare 2.times.K storage elements, K selecting circuits, K comparators, a multiplexer for selecting one symbol of K symbols, and an adder or a subtracter for a correction. It means that a correction for a lot of symbols disadvantageously requires a large amount of circuit arrangement.
The Reed-Solomon code arranges each symbol of a code word on the Galois field GF(2.sup.b) (b denotes a natural number) and an operating process of the Reed-Solomon code is performed on the Galois field.
In decoding the Reed-Solomon code, in particular, the inventors of the present invention know a decoding method operating to perform a correction for an erasure (correction to be done if where an error is located is determined) and a correction for an error (referred to as erasure plus error correction), which will be described later.
The description will be directed to the above-mentioned decoding method for correcting an erasure.
If the number h of erasure meets with a relation of 1.ltoreq.h.ltoreq.d-1, where d represents the minimum distance of the code, then the error value of erasure is obtained by solving the h-stage simultaneous linear equations of ##EQU1## where s.sub.k denotes a syndrome, X.sub.i denotes a locator of an i-th erasure, and E.sub.i denotes an error value of an i-th erasure, with h, s.sub.k and X.sub.i are known and E.sub.i is an unknown.
In order to solve the simultaneous linear equations indicated in the above expression, the following method has been used. That is, assuming that an error evaluator polynomial U(z) and an error locator polynomial .lambda. (z) are: ##EQU2## the solution of EQU E.sub.i =U (x.sub.i.sup.-i)/.lambda..sub.odd (X.sub.i.sup.-i),
with i=1, 2 . . . . . . h, can be obtained, where .lambda..sub.odd (z) stands for a sum of an odd degree components of the error locator polynomial .lambda. (z). That is, ##EQU3## where k is the largest integer which does not exceed a real number of h/2.
The term coefficients U.sub.0, U.sub.1 . . . . U.sub.h-1 of the error evaluator polynomial U (z) are allowed to be derived by the following relation of ##EQU4## Next, the description will be oriented to the decoding method for erasure plus error correction.
If m errors appear in addition to h erasure, the erasure plus error correction means obtaining an error value of an erasure and an error by solving the n-stage simultaneous linear equations of ##EQU5## where k=0, 1 . . . . . . d-2, and where n=h+m is established, X.sub.i denotes a locator of an (i-h) th error, E.sub.i denotes an error value of an (i-h) th error, with h, s.sub.k and X.sub.i (1.ltoreq.i.ltoreq.h) are known, and m, X.sub.i (h+1.ltoreq.i.ltoreq.n) and E.sub.i are unknowns. If the relation of h+2m.ltoreq.d-1 is not satisfactory, no erasure plus error correction is allowed.
The following method is used as a solution of the simultaneous linear equations indicated by the above expression. That is, like the solution for the erasure correction, assuming that the error evaluator polynomial .omega. (z) and the error locator polynomial .eta. (z) are: ##EQU6## the solution of EQU E.sub.i =.omega.(X.sub.i.sup.-i)/.eta. odd (X.sub.i.sup.-i),
with i=1,2 . . . . . . n, can be obtained, where .eta..sub.odd (z) stands for a sum of odd degree term components of the error locator polynomial .eta. (z) as follows. ##EQU7## where k is the largest integer which does not exceed a real number of n/2.
The term coefficients .omega..sub.0, .omega..sub., . . . .omega..sub.n-1 of the error evaluator polynomial .omega. (z) are obtained by the following relation of ##EQU8## In a case of performing an erasure plus error correction, since the error number m and the error locator X.sub.i (h+1.ltoreq.i.ltoreq.n) are unknown it is necessary to derive those values in advance. For this purpose, it is necessary to derive the error locator polynomial .sigma. (z) dedicated to the error and a polynomial T(z) with respect to z meeting the following expression, ##EQU9##
The error number m is obtained as the largest integer allowing the following m-degree regular matrix G.sub.h,m to be non-singular. If C.sub.h,1 is singular, m is given as m=0. If m=0, it is determined that no error but only erasure appear. Hence, the erasure correction is carried out; ##EQU10##
The error locator X.sub.h+1, X.sub.h+2. . . . X.sub.n are obtained as inverses to the roots X.sub.h+1.sup.-1, X.sub.h+2.sup.-1, . . . X.sub.n.sup.-1 of an equation .sigma.(z)=0. If only errors exist, the coefficients .sigma..sub.1, .sigma..sub.2, . . .sigma..sub.m of the error locator polynomial .sigma..sub.(z) can be uniquely obtained by solving the following linear equation of; ##EQU11##
The linear equation of the above expression will be a briefly discussed. In the previously mentioned expression, the equation .eta. (z)=.lambda.(z).sigma. (z) an the definition of T(z) result in establishing the following expression of: EQU T(z).sigma.(z)=.omega.(z) (mod z.sup.d-1)
In the above expression, .omega. (z) at the right side is a (n-1) th degree expression. Hence, the coefficients from an n-degree to (h+2m-1) th (note:h+2m.ltoreq.d-1 to h+2m-1.gtoreq.d-2) at the left side are made zero. Therefore, EQU T.sub.i .sigma..sub.0 +T.sub.i-1 .sigma..sub.1 +. . . +T.sub.i-m .sigma..sub.m =0,
with i=h+m, h+m+1 . . . . . h+2m-1,
From the expression, it is obvious that .sigma..sub.0 =1. By substituting this to the above expression, the following expression can be obtained. EQU T.sub.i-1 .sigma..sub.1 +T.sub.i-2 .sigma..sub.2 +. . . +T.sub.i-m .sigma..sub.m =T.sub.i,
with i=h+m, h+m+1 . . . . . h+2m-1,
Hence, the matrix expression of the above expression is a linear equation shown in the previously mentioned expression.
In order to perform the correction based on the decoding method for the erasure correction and the erasure plus error correction, the larger number of operations to be executed for the error plus error correction is made larger than that for the error correction. In particular, it is necessary to execute a lot of operations when obtaining the error number m and an error locator polynomial .sigma. (z) if only errors exist.
The correcting procedure can be realized by the relevant software and a computer for executing the software. For a product such as a DAT or a D-VCR, an error correcting circuit (referred to as an ECC circuit) to be operated on a microcode is developed for commercial use.
The algorithm for calculating an error number m in the erasure plus error correction will be described below as referring to the drawings. If the erasure plus error correction is executed for the erasure number h and the error number m, the maximum values h.sub.0 and m.sub.0 are preset. In carrying out the erasure plus error correction, it is necessary to meet the relation of h+2m.ltoreq.d-1, h.gtoreq.1 and m.ltoreq.1. Hence, the maximum value h.sub.0 of the from number h is d-3 and the maximum value m.sub.0 of the error number m is the largest integer which does not exceed (d-2)/2. In addition, those values h.sub.0 and m.sub.0 may be set to smaller values in order not to reduce the erroneous correctability and lower the correcting speed.
The inventors of the present invention know an algorithm of "calculating a value of m", where m.sub.0 =2.
It is determined whether or not the erasure number h is equal to or less than d-5. If h.ltoreq.d-5, the determinant .vertline.G.sub.h,2 .vertline. of the secondary square matrix G.sub.h,2 is calculated. Then, it is determined if .vertline.G.sub.h,2 .vertline. is equal to 0. If .vertline.G.sub.h,2 .vertline. is not equal to zero, m=2 is given to the algorithm. If h&gt;d-5 or .vertline.G.sub.h,2 .vertline.=0.then the determinant .vertline.G.sub.h,1 .vertline. of the primary square matrix G.sub.h,1 is calculated.
In succession, it is determined if .vertline.G.sub.h,1 .vertline. is equal to zero. If .vertline.G.sub.h,1 .vertline. is not equal to zero, m=1 is given. If .vertline.G.sub.h, 1 .vertline. =0, m=0 is given, then each determinant of .vertline.G.sub.h,2 .vertline. and .vertline.G.sub.h,1 .vertline. is calculated.
Now, the known algorithm for "calculation of .vertline.G.sub.h, m }" for executing the calculation of this determinant is described. In this algorithm, there exist steps for determining the state at each value of h in larger order such as h=3, h=4 , . . , h=h.sub.0 and steps for calculations to which the operation goes if yes is given in the former steps, although those steps are not illustrative.
At first, it is determined if the erasure number h is equal to 1. If yes, the calculation of the determinant .vertline.G.sub.1,m .vertline. is done and the operation is terminated. If no, then it is determined if a value of h is equal to 2. If yes, then the determinant of .vertline.G.sub.2,m .vertline. is calculated. Then, the operation is terminated.
If the result is negative both at the above two steps, then it is determined if h=h.sub.0 -1. If yes, the calculation of the determinant of .vertline.G.sub.h0-1,m .vertline. is performed and the calculation is terminated. If no, the calculation of the matrix .vertline.G.sub.h0,m .vertline. is performed, and the calculation is terminated.
As described above, if the erasure plus error correction is executed, the part of the program for "calculation of m" includes a branch to be done on the value of an erasure number h. The previously mentioned expression for obtaining the coefficients .sigma..sub.1, .sigma..sub.2, . . . .sigma..sub.m of the error locator polynomial .sigma.(z) for only the errors need a branch, because it refers to a value of h.
At a present time, in the field of products such as DAT, D-VCR and CD, study continues regarding the improvement of a communication speed and the reduction of a product. The error probability on data reading is made larger. The known ECC circuit basically executes the error correction and the erasure correction. It does not, in principle, perform erasure plus error correction. Hence, it is necessary to improve the error correcting probability by doing erasure plus error correction
For executing erasure plus error correction, however, it is necessary to perform many operations, thereby increasing the number of operating steps included in a microcode of the ECC circuit, resulting in making the operating speed slower.